package com.algorithm.learning.binarysearch;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/15 21:23
 **/
public class 搜索插入位置 {

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6};
        System.out.println(searchInsert(nums, 7));
    }

    /**
     * 分析:这道题要求我们在一个有序数组里查找插入元素的位置，那么什么是插入元素的位置呢?我们看示例。
     * 示例 1:目标元素5在有序数组 [1,3,5,6] 里，下标为 2，输出 2;
     * 示例 2:目标元素2不在有序数组[1,3,5,6]里，返回3的下标1，我们可以知道，如果数组中不存在目标元素返回第1个严格大于目标元素的数值的下标;
     * 示例 3:目标元素7不在有序数组 [1,3,5,6] 里。特别地，7比最后一个元素6还大，返回最后一个元素的下标 +1
     * 示例 4:目标元素0不在有序数组 [1,3,5,6] 里。特别地，0比第一个元素1还小，返回第1个元素的下标0。
     * 由上面4个示例，知道题目要我们找的是 大于等于目标元素的第1个下标。
     *
     * @param nums
     * @param target
     */
    private static int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        // [left, right]
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (target < nums[mid]) {
                // [left, mid]
                right = mid;
            } else {
                // [mid + 1, right]
                left = mid + 1;
            }
        }
        return left;
    }
}
